package leetcode.L1000;

public class EX912 {
    public static void main(String[] args) {
        int [] nums = {5,2,3,1};


        System.out.println(nums);

        for (int i = 0; i < nums.length ; i++) {
            System.out.println(nums[i]);
        }
    }
    //快速排列
    public void sort(int[] nums,int lo,int hi){
        if(lo>=hi){
            return;
        }
        int j = partition(nums,lo,hi);
        sort(nums,lo,j);
        sort(nums,j+1,hi);
    }
    public int partition(int[] nums,int lo,int hi){
        int v = nums[lo];
        int i = lo;
        int j = hi+1;
        while(true){
            while(nums[++i]<=v){if(i==hi)break;}
            while(nums[--j]>=v){if(j==lo)break;}
            if(i>=j){
                break;
            }
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
        int t = nums[lo];
        nums[lo] = nums[j];
        nums[j] = t;
        return j;
    }
    //归并排序
    static int  [] aux ;
    public static int[] sortArray_mer(int[] nums) {
        aux = new int [nums.length];
        sort_mer(nums,0,nums.length-1);
        return nums;
    }

    public static void sort_mer(int[]nums,int lo,int high){
        if(lo>=high){
            return;
        }
        int mid = lo+(high-lo)/2;
        sort_mer(nums,lo,mid);
        sort_mer(nums,mid+1,high);
        merge(nums,lo,mid,high);
    }
    public static void merge(int[]nums,int lo,int mid,int high){
        for(int i = lo;i<=high;i++){
            aux[i] = nums[i];
        }
        int j = lo,k = mid+1;

        for(int i = lo;i<=high;i++){
            if(j>mid){
                nums[i] = aux[k++];
            }
            else if(k>high){
                nums[i] = aux[j++];
            }
            else if(aux[j]>aux[k]){
                nums[i] = aux[k++];
            }
            else{
                nums[i] = aux[j++];
            }
        }
    }


    //选择排序
    public static int[] sortArray_Selection(int[] nums) {
        for(int i = 0;i<nums.length-1;i++){
            int min = i;
            for(int j = i+1;j<nums.length;j++){
                if(nums[j]<nums[min]){
                    min = j;
                }
            }
            int temp = nums[i];
            nums[i] = nums[min];
            nums[min] = temp;
        }
        return nums;
    }

}
